package org.usmile.algorithms.leetcode.hard;

import java.util.ArrayList;
import java.util.List;

/**
 * 315. 计算右侧小于当前元素的个数
 *
 * 给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。
 *
 * 示例 1：
 * 输入：nums = [5,2,6,1]
 * 输出：[2,1,1,0]
 * 解释：
 * 5 的右侧有 2 个更小的元素 (2 和 1)
 * 2 的右侧仅有 1 个更小的元素 (1)
 * 6 的右侧有 1 个更小的元素 (1)
 * 1 的右侧有 0 个更小的元素
 *
 * 示例 2：
 * 输入：nums = [-1]
 * 输出：[0]
 *
 * 示例 3：
 * 输入：nums = [-1,-1]
 * 输出：[0,0]
 *
 * 提示：
 * 1 <= nums.length <= 105
 * -104 <= nums[i] <= 104
 */
public class _0315 {
    public static void main(String[] args) {
        new _0315_Solution().countSmaller(new int[]{5,2,6,1});
    }
}

class _0315_Solution {
    private int[] smallerCount;
    private int[] indexes;

    public List<Integer> countSmaller(int[] nums) {
        smallerCount = new int[nums.length];
        indexes = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            indexes[i] = i;
        }

        mergeSort(nums, 0, nums.length - 1);

        List<Integer> result = new ArrayList<>();
        for (int count : smallerCount) {
            result.add(count);
        }

        return result;
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        merge(nums, left, mid, right);
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int[] tempNums = new int[right - left + 1];
        int[] tempIndexes = new int[right - left + 1];
        int k = 0;
        int i = left;
        int j = mid + 1;
        while (k <= right - left) {
            if (i == mid + 1) {
                tempNums[k] = nums[j];
                tempIndexes[k] = indexes[j];
                j++;
            } else if (j == right + 1) {
                tempNums[k] = nums[i];
                tempIndexes[k] = indexes[i];
                smallerCount[indexes[i]] += j - mid - 1;
                i++;
            } else if (nums[i] <= nums[j]) {
                tempNums[k] = nums[i];
                tempIndexes[k] = indexes[i];
                smallerCount[indexes[i]] += j - mid - 1;
                i++;
            } else {
                tempNums[k] = nums[j];
                tempIndexes[k] = indexes[j];
                j++;
            }
            k++;
        }

        for (k = 0; k < tempNums.length; k++) {
            nums[left] = tempNums[k];
            indexes[left] = tempIndexes[k];
            left++;
        }
    }
}